The ability to rapidly identify the frequency characteristics of an unknown signal is critical to certain applications, such as a Code Division Multiple Access (CDMA) cordless phone system. A prior method of frequency estimation uses the Fast Fourier Transform (FFT) algorithm. This process requires (PN/2) multiplications and (PN) additions, where
N=Dimension of the Transform PA0 P=Log(Base2) N PA0 1. Good, I. J., "The Interaction Algorithm and Practical Fourier Analysis", J. Roy. Statist. Soc. (London), Vol. B20, 1958. PA0 2. U.S. Pat. No. 3,879,685; Carl, J. W. et al, "Special Purpose Hybrid Computer to implement Kroneker Matrix Transformation". PA0 3. U.S. Pat. No. 3,956,619; Mundy, J. L. et al, "Pipeline Walsh-Hadamard Transformation". PA0 4. Beauchamp, K. G., "Walsh Functions and their Applications", Techniques of Physics, Ed. G. K. T. Conn and H. N. Daglish, 1977. PA0 5. Beauchamp, K. G., "Applications of Walsh and Related Functions", Academic Press, New York, New York 1984. PA0 6. U.S. Pat. No. 4,904,930 Method of Carrier Frequency Estimation; U.S. Pat. No. 4,983,906 Frequency Estimation System; U.S. Pat. No. 4,941,155 Method and Circuitry for Symbol Timing and Frequency Offset Estimation; U.S. Pat. No. 4,901,150 Automatic Noise Reduction for Individual Frequency Components of a Signal; U.S. Pat. No. 4,827,225 Fast Locking Phase-Lock Loop utilizing Frequency Estimation; U.S. Pat. No. 5,151,926 Sample Timing and Carrier Frequency Estimation Circuit for Sine-Cosine Detectors; U.S. Pat. No. 5,077,531 PSK Signal Demodulation System; U.S. Pat. No. 4,956,838 Echo Cancelling Device with Frequency Sub-Band Filtering; U.S. Pat. No. 5,165,051 Modified Fast Frequency Acquisition via Adaptive Least Square Algorithm; U.S. Pat. No. 5,148,489 Method for Spectral Estimation to Improve Noise Robustness for Speech. PA0 (1) Increase the speed of frequency estimation of an unknown signal over prior FFT methods; PA0 (2) Simplify the implementation of the frequency estimation process; PA0 (3) Improve the resolution and accuracy of this frequency estimation through data interpolation.
Disadvantages of this technique are (1) limitation of speed, and (2) difficulty in implementation; both due to the complexity of the multiplication process.
The present invention eliminates the need for multiplications altogether, through the use of the Fast Walsh Transform (FWT) algorithm, in place of the more traditional FFT method.
See e.g. the following references:
Additionally, an interpotative technique is applied to the FWT process to enhance the resolution and accuracy of frequency estimation.
Thus, the objects of the present invention are: